Password authentication protocols have been broadly deployed in client/server communication settings for its convenient usage and low costs of deployment. Nowadays peer-to-peer networks become increasingly popular, where the role of principals is symmetric (balanced), i.e. each principal acts not only as a client but also as a server.
Entity authentication that verifies the legitimacy of communication partners is indispensable for a secure communication. Basically there are two approaches for this in the network setting: relying on a PKI or using passwords. Usually the latter is preferred in practice, since authentication can be simply performed by using the human-memorable passwords without requiring the investment on the expensive PKI. Classic password authentication protocols, such as HTTP digest authentication protocol (Franks et al: HTTP Authentication: Basic and Digest Access Authentication. RFC 2617, June 1999) and Kerberos (Kohl et al.: The Kerberos Network Authentication Service (V5). RFC 1510, September 1993), are designed on the basis of the challenge-response mechanism, where the server presents the client a challenge (randomly-generated number), and the client responses to the server with a valid answer which is generated by encrypting the challenge with the password or hashing the challenge in conjunction with the password.
Although passwords are not transmitted in a clear form over the insecure network, an adversary is still able to acquire the correct password by using a special variant of the brute-force attack: the off-line dictionary attack (see Franks et al: HTTP Authentication: Basic and Digest Access Authentication. RFC 2617, June 1999; Wu: A Real-World Analysis of Kerberos Password Security. Proceedings of the ISOC Symposium on Network and Distributed System Security, 1999). This is due to the low entropy of a human-chosen password. The length of passwords mostly used in practice is rarely longer than 8 characters. It has merely about 30 bits of entropy (230) if the password is chosen by human (Burr et al.: Electronic Authentication Guideline. NIST Special publication 800-63, April 2006). Accordingly, the attacker can recover the password in a reasonable time from the recorded transcripts of a password authentication protocol.
There is password-based protocol, namely DH-EKE (“Diffie-Hellman Encrypted Key Exchange”) protocol (Bellovin et al.: Encrypted Key Exchange: Password-based Protocols Secure against Dictionary Attacks. Proceedings of the IEEE Symposium on Research in Security and Privacy, May 1992), proposed to foil off-line dictionary attacks. Its basic idea is that two parties exchange ephemeral DH public keys encrypted with a shared password. Only the parties who know the password are able to agree upon a session key for securing the communication. The protocol addresses a problem that seems to be intractable in the past: the establishment of a cryptographically strong session key from a shared short secret with low entropy.
Inspired by the DH-EKE protocol, numerous password-based authentication key agreement protocols have been developed, most of which follow the principle of DH-EKE protocol. They are distinguished in two categories: augmented and balanced password-authenticated key agreement protocols. The augmented password-authenticated key agreement protocols are mainly used in client/server settings, where the client (user) knows the password, whilst the server possesses only the password verifiers for authenticating clients. The SRP (“Secure Remote Password”) protocol (Wu: The Secure Remote Password Protocol. Proceedings of the 1998 Internet Society Network and Distributed System Security Symposium, San Diego, March 1998, pp. 97-111) and AMP (“Authentication via Memorable Password”) protocol (Kwon: Authentication and Key Agreement via Memorable Password. NDSS 2001 Symposium Conference Proceedings, February 2001) are typical examples.
The balanced password-authenticated key agreement (BPAKA) protocol is a symmetric authentication scheme, where both parties know a common password and negotiate a shared session key after the successful mutual authentication by using the password. This protocol is well suited for symmetric communication settings, where the roles of the principals are balanced like in peer-to-peer (P2P) communication, wireless mesh networks, and wireless ad-hoc networks. There are several representative protocols in this category. They are DH-EKE protocol, PAK (“Password Authenticated Key exchange”) protocol (MacKenzie: The PAK Suite: Protocols for Password-Authenticated Key Exchange DIMACS Technical Report 002-46, October 2002), SPEKE (“Secure Password Exponential Key Exchange”) protocol (Jablon: Strong Password-Only Authenticated Key Exchange Computer Communication Review, ACM SIGCOMM, vol. 26, no. 5, pp. 5-26, October 1996), as well as the newcomer J-PAKE (Hao et al.: Password Authenticated Key Exchange by Juggling. Proceedings of the 16th International Workshop on Security Protocols, 2008).
The DH-EKE protocol first demonstrated that it is feasible to withstand off-line dictionary attacks in an authenticated key agreement protocol. This has been achieved by symmetrically encrypting the exchanged DH public keys with the shared password. The only difference between the DH-EKE protocol and the basic Diffie-Hellman protocol is that the exchanged DH public keys are encrypted in the DH-EKE protocol with the password, whilst in the basic DH protocol they are not. The encryption of the exchanged DH public keys serves two purposes. First it provides an authentication function in the sense that only the parties who know the password can correctly decrypt the DH public keys and generate the session key according to the basic DH principle. Secondly it can foil off-line dictionary attacks because an attacker is unable to ascertain whether the decryption results are valid messages, when decrypting the encrypted DH public keys using a guessed password. However, as shown in (Patel: Number theoretic attacks on secure password schemes. Proceedings of the IEEE Symposium on Security and Privacy, May 1997; Patel: Information Leakage in Encrypted Key Exchange. Proceedings of the DIMACS Workshop on Network Threats, 1997), the DH-EKE protocol suffers from partition attacks due to information leakage. Assume that a DH public key gx mod p is encrypted with a password, where p is a prime number encoded with n bits so that p≦2n−1. An attacker can mount partition attacks to rule out the guessing password candidates which are used for decrypting the DH public keys, when the decryption results fall into the range [p, 2n−1]. To decrease the possibility of a partition attack, p should be slightly less than a power of 2, and a certain number of the most significant bits of p are set one. This implies that the domain parameters have to be carefully chosen in the discrete logarithm (DL) groups and specific finite groups needed to be defined. Another limitation of DH-EKE is that the use of the short exponents makes the scheme insecure (Hao: Password Authenticated Key Exchange by Juggling. Proceedings of the 16th International Workshop on Security Protocols, 2008). This makes the protocol much more inefficient than those protocols that can utilize short exponents.
Although the DH-EKE protocol has several security weaknesses and performance limitations, it creates a new concept to realize the password authentication key agreement protocol. This concept is generalized as follows: the parties can mutually authenticate each other and agree upon a shared key through exchanging the password-entangled public keys The protocol SPEKE (“secure password exponential key exchange”) instantiates the DH-EKE concept using a password-driven variable as generator of the public keys instead of a fixed one as in the basic DH protocol. However, such method allows an active attacker to test multiple passwords in one run of the protocol because some passwords are exponentially equivalent. It may become more serious that an attacker is possible to recover the password if the password is a Personal Identification Number (PIN). Like the DH-EKE protocol, the SPEKE protocol has to use long exponents (Hao: Password Authenticated Key Exchange by Juggling. Proceedings of the 16th International Workshop on Security Protocols, 2008). The password authenticated key (PAK) exchange protocol is another scheme following the generic concept. It employs the multiplication operation in the DL group to replace the symmetric encryption operation used in the DH-EKE protocol. The DH public keys in the PAK protocol are multiplied with a password-driven group element rather than are encrypted with a password before they are exchanged. The short exponents can be applied to the generation of the DH public keys in the PAK protocol. But an exponentiation with the long exponent is needed to convert the hash value of the password into the DL group element. This calculation is more expensive than the subsequent DH exchange computation.
Recently a new solution to the password authenticated key exchange called J-PAKE (Password Authenticated Key Exchange by Juggling) was proposed (Hao: Password Authenticated Key Exchange by Juggling. Proceedings of the 16th International Workshop on Security Protocols, 2008). Its design concept is completely different from the past password authenticated key exchange protocols. The J-PAKE protocol works like a juggling game between two players if we view a public key as a “ball”. In round one, each player throws two balls (ephemeral public keys) to each other. In round two, each player forms a new ball by combining the available public keys and the password, and throws it to each other. After that, two parties can compute a common session key if the same password is provided in the calculation of the session key. The J-PAKE imposes no constraints on the choice of finite groups and use of the short exponents. But the performance of the J-PAKE is merely comparable to that of the aforementioned protocols (DH-EKE, SPEKE, and PAK) because it needs 14 exponentiations using short exponents in each party to complete the protocol, whilst the previous protocols requires only two exponentiations with long exponents.
It is well-known that security protocols are difficult to design because they have to fulfill numerous security requirements and simultaneously to be efficient. They should possess the following security properties: key authentication, known-key security, forward secrecy, off-line dictionary at-tack resistance, partition attack resistance, on-line dictionary attack resistance. Although several BPAKA protocols are available, their weaknesses in terms of security and efficiency are gradually disclosed.